package _18_剑指OfferII;

import java.util.Stack;

public class _037_剑指OfferII小行星碰撞 {

    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> stack = new Stack<>();

        for (int asteroid : asteroids) {
            if (stack.isEmpty() || stack.peek() < 0 || asteroid > 0) {
                stack.push(asteroid);
            } else {
                while (stack.peek() < -asteroid) {
                    stack.pop();
                    if (stack.isEmpty() || stack.peek() < 0) {
                        stack.push(asteroid);
                        break;
                    }
                }
                // 弹出相同元素
                if (stack.peek() == -asteroid) stack.pop();
            }
        }

        int[] results = new int[stack.size()];
        int index = results.length;
        while (!stack.isEmpty()) {
            results[--index] = stack.pop();
        }
        return results;
    }

}
